Problem :

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police.

Example 1 :

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2 :

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

核心思維 :

1. 設定nums代表每個房子的金額

• 若nums為空則回傳0
• 若nums只有一個元素回傳該元素的值

2. 初始化dp向量，儲存每一步的最大金額

• 第一間房子的最大金額就是第一間房子有的金額
• 第二間房子的最大金額是第一間和第二間房子金額較大者
• 從第三個房子開始計算，dp[i] 是選擇當前房子或不選擇的最大金額，若選擇當前房子加上 dp[i - 2] 的值，反之則取 dp[i - 1] 的值

3. 回傳所有房子可以獲取的最大金額

程式碼 :

class Solution {
public:
    int rob(vector<int>& nums) {
        //若nums為空則回傳0
        if(nums.size() == 0){
            return 0;
        }
        //若nums只有一個元素則回傳該元素的值
        if(nums.size() == 1){
            return nums[0];
        }
        //初始化dp向量，儲存每一步的最大金額
        std::vector<int> dp(nums.size());
        //第一間房子的最大金額就是第一間房子有的金額
        dp[0] = nums[0];
        //第二間房子的最大金額是第一間和第二間房子金額較大者
        dp[1] = std::max(nums[0], nums[1]);
        //從第三個房子開始計算
        for(int i = 2; i < nums.size(); i++){
            //dp[i] 是選擇當前房子或不選擇的最大金額，若選擇當前房子加上 dp[i - 2] 的值，反之則取 dp[i - 1] 的值
            dp[i] = std::max(dp[i-1], dp[i-2] + nums[i]);
        }
        //回傳所有房子可以獲取的最大金額
        return dp[nums.size() - 1];
    }
};

結論 :

這題的目標是在有限的選擇內打劫房屋並獲取最大的金額，透過動態規劃的方法來確定從房子中可以獲取的最大金額。利用一個dp陣列來記錄在每個房子打劫的最佳選擇，程式碼能夠計算出每一步的選擇，最終返回整體的最大獲利值。這段程式碼的時間複雜度為 O(n)，可以處理大規模輸入的問題，同時簡潔明瞭，易於理解。